/*
 * @lc app=leetcode.cn id=457 lang=cpp
 *
 * [457] 环形数组是否存在循环
 */

// @lc code=start
class Solution
{
public:
    int getNext(int idx, int n, vector<int> &nums)
    {
        return ((idx + nums[idx] % n) + n) % n;
    }
    bool circularArrayLoop(vector<int> &nums)
    {
        int n = nums.size();
        for (int i = 0; i < n; i++)
        {
            int slow = i;
            int fast = getNext(i, n, nums);

            while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[getNext(fast, n, nums)] > 0)
            {
                if (slow == fast)
                {
                    if (slow == getNext(slow, n, nums))
                        break;
                    return true;
                }
                slow = getNext(slow, n, nums);
                fast = getNext(getNext(fast, n, nums), n, nums);
            }
        }

        return false;
    }
};
// @lc code=end
